package com.caoyanan.algorithm.question.zuoTraining.training003.class06;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 给定一个正数数组arr，返回该数组能不能分成4个部分，并且每个部分的累加和相等，切分位置的数不要。
 * 例如:
 * arr=[3, 2, 4, 1, 4, 9, 5, 10, 1, 2, 2] 返回true
 * 三个切割点下标为2, 5, 7. 切出的四个子数组为[3,2], [1,4], [5], [1,2,2]，
 * 累加和都是5
 * @author: caoyanan
 * @time: 2021/4/26 4:34 下午
 */
public class Question06_Split4Parts {

    public static int[] canSplit(int[] arr) {
        Map<Integer, Integer> sumIndex = new HashMap<>(arr.length);
        int sum = arr[0];

        // 这里的前缀和预处理map是前缀和对应的下一个位置
        for (int i = 1; i < arr.length; i++) {
            sumIndex.put(sum, i);
            sum += arr[i];
        }
        int partSum = arr[0];
        for (int firstIndex = 1; firstIndex < arr.length - 6; partSum += arr[firstIndex],firstIndex++) {
            Integer secondIndex = sumIndex.get(2 * partSum + arr[firstIndex]);
            if (Objects.isNull(secondIndex)) {
                continue;
            }
            Integer thirdIndex = sumIndex.get(3 * partSum + arr[firstIndex] + arr[secondIndex]);
            if (Objects.isNull(thirdIndex)) {
                continue;
            }
            if (sum != 4 * partSum + arr[firstIndex] + arr[secondIndex] + arr[thirdIndex]) {
                continue;
            }
            return new int[]{firstIndex, secondIndex, thirdIndex};
        }
        return null;
    }

    public static void main(String[] args) {
        LogarithmInputGenerator instance = LogarithmInputGenerator.getInstance();
        for (int i = 10; i < 20; i++) {
            for (int j = 1; j <= 300000; j++) {
                int[] inputs = instance.generateRandomArray(i, 20);
                int[] result = canSplit(inputs);
                if (Objects.nonNull(result)) {
                    System.out.println("输入:"+ Arrays.toString(inputs));
                    System.out.println("切割结果:" + Arrays.toString(result));
                    System.out.println();
                }
            }
        }
    }
}
